package 每日一题;

public class No115不同的子序列 {

    /**
     * 给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
     * 字符串的一个 子序列 是指，
     * 通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。
     * （例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）
     * 题目数据保证答案符合 32 位带符号整数范围。
     *
     * 示例 1：
     * 输入：s = "rabbbit", t = "rabbit"
     * 输出：3
     * 解释：
     * 如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
     * (上箭头符号 ^ 表示选取的字母)
     * rabbbit
     * ^^^^ ^^
     * rabbbit
     * ^^ ^^^^
     * rabbbit
     * ^^^ ^^^
     * 示例 2：
     * 输入：s = "babgbag", t = "bag"
     * 输出：5
     * 解释：
     * 如下图所示, 有 5 种可以从 s 中得到 "bag" 的方案。
     * (上箭头符号 ^ 表示选取的字母)
     * babgbag
     * ^^ ^
     * babgbag
     * ^^    ^
     * babgbag
     * ^    ^^
     * babgbag
     *   ^  ^^
     * babgbag
     *     ^^^
     *
     * 提示：
     * 0 <= s.length, t.length <= 1000
     * s 和 t 由英文字母组成
     */

    public int numDistinct(String s, String t) {

        if(s==null||s.length()==0){
            return 0;
        }
        if(t==null||t.length()==0){
            return 0;
        }

        char[] sArr = s.toCharArray();
        char[] tArr = t.toCharArray();
        int[][] dp=new int[t.length()][s.length()];

        //base
        if(sArr[0]==tArr[0]){
            dp[0][0]=1;
        }
        for (int i = 1; i < s.length(); i++) {
            if(sArr[i]==tArr[0]){
                dp[0][i]=dp[0][i-1]+1;
            }else{
                dp[0][i]=dp[0][i-1];
            }
        }

        //然后开始
        for (int i = 1; i < t.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                if(tArr[i]==sArr[j]){
                    dp[i][j]=dp[i][j-1]+dp[i-1][j-1];
                }else{
                    dp[i][j]=dp[i][j-1];
                }
            }
        }

        return dp[t.length()-1][s.length()-1];
    }

}
